Unique paths III [Backtracking DFS]¶
Time: O((MxN)2^(MxN)); Space: O((MxN)2^(MxN)); hard
On a 2-dimensional grid, there are 4 types of squares:
1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.
Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.
Example 1:
Input: grid =
[
[1,0,0,0],
[0,0,0,0],
[0,0,2,-1]
]
Output: 2
Explanation:
We have the following two paths:
(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
Example 2:
Input: grid =
[
[1,0,0,0],
[0,0,0,0],
[0,0,0,2]
]
Output: 4
Explanation:
We have the following four paths:
(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
(0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
(0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
Example 3:
Input: grid =
[
[0,1],
[2,0]
]
Output: 0
Explanation:
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.
Constraints:
1 <= len(grid) * len(grid[0]) <= 20
1. Dynamic Programming [O(MxNx2^(MxN)), O(MxNx2^(MxN)))]¶
[14]:
class Solution1(object):
"""
Time: O(M*N*2^(M*N))
Space: O(M*N*2^(M*N))
"""
def uniquePathsIII(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def index(grid, r, c):
return 1 << (r*len(grid[0])+c)
def dp(grid, src, dst, todo, lookup):
if src == dst:
return int(todo == 0)
key = (src, todo)
if key in lookup:
return lookup[key]
result = 0
for d in directions:
r, c = src[0]+d[0], src[1]+d[1]
if 0 <= r < len(grid) and \
0 <= c < len(grid[0]) and \
grid[r][c] % 2 == 0 and \
todo & index(grid, r, c):
result += dp(grid, (r, c), dst, todo ^ index(grid, r, c), lookup)
lookup[key] = result
return lookup[key]
todo = 0
src, dst = None, None
for r, row in enumerate(grid):
for c, val in enumerate(row):
if val % 2 == 0:
todo |= index(grid, r, c)
if val == 1:
src = (r, c)
elif val == 2:
dst = (r, c)
return dp(grid, src, dst, todo, {})
[15]:
s = Solution1()
grid = [
[1,0,0,0],
[0,0,0,0],
[0,0,2,-1]
]
assert s.uniquePathsIII(grid) == 2
grid = [
[1,0,0,0],
[0,0,0,0],
[0,0,0,2]
]
assert s.uniquePathsIII(grid) == 4
grid = [
[0,1],
[2,0]
]
assert s.uniquePathsIII(grid) == 0
2. Dynamic Programming [O(RxCx2^(RxC)), O(RxC)]¶
Intuition and Algorithm
Let dp(r, c, todo) be the number of paths starting from where we are (r, c), and given that todo is the set of empty squares we’ve yet to walk on.
We can use a similar approach to Approach 1, except we will memoize these states (r, c, todo) so as not to repeat work.
[16]:
from functools import lru_cache
class Solution2(object):
"""
Time: O(R*C*2^(R*C)), where R, C are the number of rows and columns in the grid
Space: O(R*cC)
"""
def uniquePathsIII(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
R, C = len(grid), len(grid[0])
def code(r, c):
return 1 << (r * C + c)
def neighbors(r, c):
for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] % 2 == 0:
yield nr, nc
target = 0
for r, row in enumerate(grid):
for c, val in enumerate(row):
if val % 2 == 0:
target |= code(r, c)
if val == 1:
sr, sc = r, c
if val == 2:
tr, tc = r, c
@lru_cache(None)
def dp(r, c, todo):
if r == tr and c == tc:
return +(todo == 0)
ans = 0
for nr, nc in neighbors(r, c):
if todo & code(nr, nc):
ans += dp(nr, nc, todo ^ code(nr, nc))
return ans
return dp(sr, sc, target)
[17]:
s = Solution2()
grid = [
[1,0,0,0],
[0,0,0,0],
[0,0,2,-1]
]
assert s.uniquePathsIII(grid) == 2
grid = [
[1,0,0,0],
[0,0,0,0],
[0,0,0,2]
]
assert s.uniquePathsIII(grid) == 4
grid = [
[0,1],
[2,0]
]
assert s.uniquePathsIII(grid) == 0
3. Backtracking DFS¶
Intuition and Algorithm
Let’s try walking to each 0, leaving an obstacle behind from where we walked. After, we can remove the obstacle.
Given the input limits, this can work because bad paths tend to get stuck quickly and run out of free squares.
[18]:
class Solution3(object):
def uniquePathsIII(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
R, C = len(grid), len(grid[0])
def neighbors(r, c):
for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] % 2 == 0:
yield nr, nc
todo = 0
for r, row in enumerate(grid):
for c, val in enumerate(row):
if val != -1: todo += 1
if val == 1: sr, sc = r, c
if val == 2: tr, tc = r, c
self.ans = 0
def dfs(r, c, todo):
todo -= 1
if todo < 0:
return
if r == tr and c == tc:
if todo == 0:
self.ans += 1
return
grid[r][c] = -1
for nr, nc in neighbors(r, c):
dfs(nr, nc, todo)
grid[r][c] = 0
dfs(sr, sc, todo)
return self.ans
[19]:
s = Solution3()
grid = [
[1,0,0,0],
[0,0,0,0],
[0,0,2,-1]
]
assert s.uniquePathsIII(grid) == 2
grid = [
[1,0,0,0],
[0,0,0,0],
[0,0,0,2]
]
assert s.uniquePathsIII(grid) == 4
grid = [
[0,1],
[2,0]
]
assert s.uniquePathsIII(grid) == 0